Adding some more judges, here and there.

[and.git] / lib / Mi manual de algoritmos / version_actual / src / grafos / kruskal.tex

% Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite

{\ttfamily \raggedright {
\noindent
\mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$iostream$>$}} \\
\mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$vector$>$}} \\
\mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$algorithm$>$}} \\
\mbox{} \\
\mbox{}\textbf{\textcolor{Blue}{using}}\ \textbf{\textcolor{Blue}{namespace}}\ std\textcolor{BrickRed}{;} \\
\mbox{} \\
\mbox{}\textit{\textcolor{Brown}{/*}} \\
\mbox{}\textit{\textcolor{Brown}{Algoritmo\ de\ Kruskal,\ para\ encontrar\ el\ árbol\ de\ recubrimiento\ de\ mínima\ suma.}} \\
\mbox{}\textit{\textcolor{Brown}{*/}} \\
\mbox{} \\
\mbox{}\textbf{\textcolor{Blue}{struct}}\ edge\textcolor{Red}{\{} \\
\mbox{}\ \ \textcolor{ForestGreen}{int}\ start\textcolor{BrickRed}{,}\ end\textcolor{BrickRed}{,}\ weight\textcolor{BrickRed}{;} \\
\mbox{}\ \ \textcolor{ForestGreen}{bool}\ \textbf{\textcolor{Blue}{operator}}\ \textcolor{BrickRed}{$<$}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{const}}\ edge\ \textcolor{BrickRed}{\&}that\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{const}}\ \textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \textit{\textcolor{Brown}{//Si\ se\ desea\ encontrar\ el\ árbol\ de\ recubrimiento\ de\ máxima\ suma,\ cambiar\ el\ $<$\ por\ un\ $>$}} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{return}}\ weight\ \textcolor{BrickRed}{$<$}\ that\textcolor{BrickRed}{.}weight\textcolor{BrickRed}{;} \\
\mbox{}\ \ \textcolor{Red}{\}} \\
\mbox{}\textcolor{Red}{\}}\textcolor{BrickRed}{;} \\
\mbox{} \\
\mbox{} \\
\mbox{}\textit{\textcolor{Brown}{/*\ Union\ find\ */}} \\
\mbox{}\textcolor{ForestGreen}{int}\ p\textcolor{BrickRed}{[}\textcolor{Purple}{10001}\textcolor{BrickRed}{],}\ rank\textcolor{BrickRed}{[}\textcolor{Purple}{10001}\textcolor{BrickRed}{];} \\
\mbox{}\textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{make$\_$set}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ x\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ p\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ x\textcolor{BrickRed}{,}\ rank\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;}\ \textcolor{Red}{\}} \\
\mbox{}\textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{link}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ x\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ y\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ rank\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{$>$}\ rank\textcolor{BrickRed}{[}y\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{?}\ p\textcolor{BrickRed}{[}y\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ x\ \textcolor{BrickRed}{:}\ p\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ y\textcolor{BrickRed}{,}\ rank\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{==}\ rank\textcolor{BrickRed}{[}y\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{?}\ rank\textcolor{BrickRed}{[}y\textcolor{BrickRed}{]++:}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;}\ \textcolor{Red}{\}} \\
\mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{find$\_$set}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ x\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ \textbf{\textcolor{Blue}{return}}\ x\ \textcolor{BrickRed}{!=}\ p\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{?}\ p\textcolor{BrickRed}{[}x\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{find$\_$set}}\textcolor{BrickRed}{(}p\textcolor{BrickRed}{[}x\textcolor{BrickRed}{])}\ \textcolor{BrickRed}{:}\ p\textcolor{BrickRed}{[}x\textcolor{BrickRed}{];}\ \textcolor{Red}{\}} \\
\mbox{}\textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{merge}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ x\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ y\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ \textbf{\textcolor{Black}{link}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{find$\_$set}}\textcolor{BrickRed}{(}x\textcolor{BrickRed}{),}\ \textbf{\textcolor{Black}{find$\_$set}}\textcolor{BrickRed}{(}y\textcolor{BrickRed}{));}\ \textcolor{Red}{\}} \\
\mbox{}\textit{\textcolor{Brown}{/*\ End\ union\ find\ */}} \\
\mbox{} \\
\mbox{} \\
\mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{main}}\textcolor{BrickRed}{()}\textcolor{Red}{\{} \\
\mbox{}\ \ \textcolor{ForestGreen}{int}\ c\textcolor{BrickRed}{;} \\
\mbox{}\ \ cin\ \textcolor{BrickRed}{$>$$>$}\ c\textcolor{BrickRed}{;} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}c\textcolor{BrickRed}{-\/-)}\textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ n\textcolor{BrickRed}{,}\ m\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ n\ \textcolor{BrickRed}{$>$$>$}\ m\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ vector\textcolor{BrickRed}{$<$}edge\textcolor{BrickRed}{$>$}\ e\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \textcolor{ForestGreen}{long}\ \textcolor{ForestGreen}{long}\ total\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}m\textcolor{BrickRed}{-\/-)}\textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \ \ edge\ t\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ t\textcolor{BrickRed}{.}start\ \textcolor{BrickRed}{$>$$>$}\ t\textcolor{BrickRed}{.}end\ \textcolor{BrickRed}{$>$$>$}\ t\textcolor{BrickRed}{.}weight\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \ \ e\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{push$\_$back}}\textcolor{BrickRed}{(}t\textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \ \ total\ \textcolor{BrickRed}{+=}\ t\textcolor{BrickRed}{.}weight\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \textcolor{Red}{\}} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Black}{sort}}\textcolor{BrickRed}{(}e\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{begin}}\textcolor{BrickRed}{(),}\ e\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{end}}\textcolor{BrickRed}{());} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$=}n\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \ \ \textbf{\textcolor{Black}{make$\_$set}}\textcolor{BrickRed}{(}i\textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \textcolor{Red}{\}} \\
\mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}e\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \ \ \textcolor{ForestGreen}{int}\ u\ \textcolor{BrickRed}{=}\ e\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}start\textcolor{BrickRed}{,}\ v\ \textcolor{BrickRed}{=}\ e\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}end\textcolor{BrickRed}{,}\ w\ \textcolor{BrickRed}{=}\ e\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}weight\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Black}{find$\_$set}}\textcolor{BrickRed}{(}u\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{!=}\ \textbf{\textcolor{Black}{find$\_$set}}\textcolor{BrickRed}{(}v\textcolor{BrickRed}{))}\textcolor{Red}{\{} \\
\mbox{}\ \ \ \ \ \ \ \ \textit{\textcolor{Brown}{//printf("{}Joining\ \%d\ with\ \%d\ using\ weight\ \%d\textbackslash{}n"{},\ u,\ v,\ w);}} \\
\mbox{}\ \ \ \ \ \ \ \ total\ \textcolor{BrickRed}{-=}\ w\textcolor{BrickRed}{;} \\
\mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Black}{merge}}\textcolor{BrickRed}{(}u\textcolor{BrickRed}{,}\ v\textcolor{BrickRed}{);} \\
\mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
\mbox{}\ \ \ \ \textcolor{Red}{\}} \\
\mbox{}\ \ \ \ cout\ \textcolor{BrickRed}{$<$$<$}\ total\ \textcolor{BrickRed}{$<$$<$}\ endl\textcolor{BrickRed}{;} \\
\mbox{} \\
\mbox{}\ \ \textcolor{Red}{\}} \\
\mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
\mbox{}\textcolor{Red}{\}} \\

} \normalfont\normalsize